Search results for "Īpašību testēšana"

Monotonitātes testēšana uz līnijas

2020

Darbā tiek aplūkota īpašību testēšanas paradigma un monotonitātes testēšana uz līnijas jeb funkcijas. Īpašību testēšanas paradigma ir saistīta ar apakš-lineāru algoritmu konstruēšanu, kas piekļūst tikai daļai no datiem. Balstoties uz šiem datiem, algoritms ar kādu varbūtību var noteikt, vai datiem piemīt īpašība. Pēc paradigmas principiem, algoritmam ir jāspēj noskaidrot, vai dotais datu apjoms ir monotons ātrāk, nekā lineārā laikā. Labākais iepriekšējais rezultāts monotonitātes pārbaudei funkcijai f:[n] --> [r] ir Theta(log(epsilon n)/epsilon) pie epsilon 1/2, tas ir funkcijām, kas ir ļoti tālu no monotonām. Darbā tiks pierādīta apakšējā robeža monotonitātes pārbaudei funkcijām pie epsilon…